{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e6125305-22d4-4ea9-8568-f33018e335d9",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/lru-cache\n",
    "\n",
    "\n",
    "Time Limit Exceeded\n",
    "\n",
    "\n",
    "```cpp\n",
    "class LRUCache {\n",
    "public:\n",
    "    vector<int> history;\n",
    "    map<int, int> dict_;\n",
    "    int capacity;\n",
    "    LRUCache(int capacity) {\n",
    "      //4:51\n",
    "      history.clear();\n",
    "      dict_.clear();\n",
    "      this->capacity = capacity;\n",
    "      //5:03\n",
    "    }\n",
    "    \n",
    "    int get(int key) {\n",
    "      if (dict_.find(key) == dict_.end()) {\n",
    "        return -1;\n",
    "      } else {\n",
    "        auto found = find(history.begin(), history.end(), key);\n",
    "        if (found != history.end()) {\n",
    "          history.erase(found);\n",
    "        }\n",
    "        history.push_back(key);\n",
    "        return dict_[key];\n",
    "      }\n",
    "    }\n",
    "    \n",
    "    void put(int key, int value) {\n",
    "      if (dict_.find(key) == dict_.end()) {\n",
    "        // not found\n",
    "        if (history.size() >= capacity) {\n",
    "          auto old_key = history[0];\n",
    "          vector<int> sub_list(history.begin()+1, history.end());\n",
    "          history = sub_list;\n",
    "          dict_.erase(old_key);\n",
    "        }\n",
    "        dict_[key] = value;\n",
    "        history.push_back(key);\n",
    "\n",
    "      } else {\n",
    "        // found\n",
    "        auto found = find(history.begin(), history.end(), key);\n",
    "        if (found != history.end()) {\n",
    "          history.erase(found);\n",
    "        }\n",
    "        history.push_back(key);\n",
    "        dict_[key] = value;\n",
    "      }\n",
    "    }\n",
    "};\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e28da4f1-8a05-434c-93ef-e008369a484a",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": ""
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}